package jianzhi_offer;

public class _27_数组中出现次数超过一半的数字 {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0) return 0;
        int now = array[0];
        int count = 1;
        for(int i=1;i<array.length;++i){
            if(count == 0){
                now = array[i];
                count = 1;
            }else if(array[i] == now) ++count;
            else{
                --count;
                if(count == 0) now = 0;
            }
        }
        //确定这个now是不是最终答案
        count = 0;
        for(int i:array){
            if(i == now) ++count;
        }
        return count>array.length/2?now:0;
    }
}
